package greedy

import "math"

// https://leetcode-cn.com/problems/minimum-size-subarray-sum/
// 最小子数组长度，子数组元素和必须大于等于target
// 解法: 贪心算法，标记左右两个位置，一直向右移动，并在每一步 都判断左节点是否可以向右移动，以减小数组长度
// 时间复杂度: O(n)
func MinSubArrayLen(target int, nums []int) int {
	if len(nums) == 0 || target == 0 {
		return 0
	}
	left, right := 0, 0
	minLen := math.MaxInt32
	currentSum := nums[0]
	currentLen := 1
	for {
		if currentSum >= target {
			if currentLen < minLen {
				minLen = currentLen
			}
			// 情况1: 左节点可以向右移动
			if left < right && currentSum-nums[left] >= target {
				currentSum -= nums[left]
				left++
				currentLen--
				continue
			}
		}
		// 普通情况: 右节点向右移动
		if right < len(nums)-1 {
			right++
			currentSum += nums[right]
			currentLen++
		} else {
			break
		}
	}
	if minLen == math.MaxInt32 {
		return 0
	}
	return minLen
}
